package leet.ku._102;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}

public class Solution {
	public List<List<Integer>> levelOrder(TreeNode root) {
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		if (root == null)
			return result;
		
		List<TreeNode> lastLevel = Arrays.asList(root);
		result.add(Arrays.asList(root.val));
		while (!lastLevel.isEmpty()) {
			List<TreeNode> thisLevel = new ArrayList<TreeNode>();
			List<Integer> line = new ArrayList<Integer>();
			for (TreeNode node : lastLevel) {
				if (node.left != null) {
					thisLevel.add(node.left);
					line.add(node.left.val);
				}
				if (node.right != null) {
					thisLevel.add(node.right);
					line.add(node.right.val);
				}
			}
			if (!line.isEmpty())
				result.add(line);
			lastLevel = thisLevel;
		}
		return result;
	}
}